/**
 * 最长公共子序列的动态规划解法，跟01背包是类似的
 * @param wordX 字符串X
 * @param wordY 字符串Y
 */
export function lcs(wordX: string, wordY: string) {
    const m = wordX.length;
    const n = wordY.length;
    // 记忆化，维度是两个字符串具体字符，值就是长度（解）
    const l: number[][] = [];
    // 方案存储
    const solution: string[][] = [];

    // 初始化l和solution
    for (let i = 0; i <= m; i++) {
        l[i] = [];
        solution[i] = [];
        for (let j = 0; j <= n; j++) {
            l[i][j] = 0;
            solution[i][j] = '0';
        }
    }

    // 两个字符串的嵌套循环
    for (let i = 0; i <= m; i++) {
        for (let j = 0; j <= n; j++) {
            // 同样的，索引为0时，其解为0
            if (i === 0 || j === 0) {
                l[i][j] = 0;
            }
            // 其两个位置的字符相同，解也就是长度，要在前一个相同字符的解上加一
            else if (wordX[i - 1] === wordY[j - 1]) {
                l[i][j] = l[i - 1][j - 1] + 1;
                // 对角线，也就是字符第一次匹配上的时候
                solution[i][j] = 'diagonal';
            } else {
                // 不相同的话需要与前面的解保持一致，但是要取一个最优解
                const a = l[i - 1][j];
                const b = l[i][j - 1];
                l[i][j] = a > b ? a : b; // max(a,b)
                solution[i][j] = l[i][j] === l[i - 1][j] ? 'top' : 'left';
            }
        }
    }

    return printSolution(solution, wordX, m, n);
}
/**
 * 求出该问题最优解的具体方案
 * @param solution 方案存储
 * @param wordX 其中的一个字符串
 * @param m 字符串X的长度
 * @param n 字符串Y的长度
 */
function printSolution(solution: string[][], wordX: string, m: number, n: number) {
    let a = m;
    let b = n;
    let x = solution[a][b];
    let answer = '';
    // 从尾部往上遍历才会得到以wordX为主视角的最长公共子序列
    while (x !== '0') {
        // 只有当是对角线时，才是刚刚匹配到的位置
        if (solution[a][b] === 'diagonal') {
            answer = wordX[a - 1] + answer;
            a--;
            b--;
        } else if (solution[a][b] === 'left') {
            b--;
        } else if (solution[a][b] === 'top') {
            a--;
        }
        x = solution[a][b];
    }

    return answer;
}
